package demo.practice.leetcode_msjd;

import java.util.ArrayList;
import java.util.List;

public class M1003 {

    public static void main(String[] args) {
        M1003 m1003= new M1003();
        m1003.search(new int[]{5,5,5,1,2,3,4,5},5);
    }

    public int search(int[] arr, int target) {

        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();

        List<Integer> cur = l1;
        int j=0;
        for (int i = 0; i < arr.length-1; i++) {
            cur.add(arr[i]);
            if(arr[i]>arr[i+1]){
                cur=l2;
                j=i+1;//前面有i+1个数
            }

        }
        cur.add(arr[arr.length-1]);

        l2.addAll(l1);
        int s=search(l2,target);
        return s==-1 ?-1:(s+j)%arr.length;
    }

    public int search(List<Integer>  list, int target){

        return search(list,target,0,list.size()-1);
    }

    public int search(List<Integer>  list, int target,int minindex,int maxindex){

        if(list.get(minindex)==target)
            return minindex;

        if(list.get(maxindex)==target)
            return maxindex;

        if(minindex>=maxindex)
            return -1;

        int middle=minindex+(maxindex-minindex)/2;
        if(list.get(middle)==target)
            return middle;

        if(list.get(middle)>target) //中间值大于目标值，则在前面找
            return search(list,target,minindex,middle-1);
        else                        //中间值小于目标值，则在后面找
            return search(list,target,middle+1,maxindex);

    }

}
